package LearnAlgorithm.g_数学问题;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/*
用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量
如果有无限个砝码,但它们的重量分别是1 , 3, 9, 27, 81。.... 等3的指数幂
神奇之处在于用它们的组合可以称出任意整数重量(砝码允许放在左右两个盘中)
本题目要求编程实现:对用户给定的重量,给出砝码组合方案,重量 < 1000000
例如:
用户输入:
5
程序输出:
9 - 3 - 1
 */
public class a天平秤重by巧用进制 {
	public static void main(String[] args) {
		ternaryScale();
		violence(7);
	}
	
	public static void ternaryScale() {
		Scanner sc = new Scanner(System.in);
		int number = sc.nextInt();
		final String stringNumber = Integer.toString(number,3);
		char[] arr = new StringBuilder(stringNumber).reverse().toString().toCharArray();//翻转后转成字符数组；从低位到高位处理
		List<Integer> list = new ArrayList<Integer>();//创建存放处理后的三进制数的容器；arraylist索引从0到高，代表着三进制数的数位从高到低
		/*
		void  add（int index, E element）：可以在插入操作过程中指定插入的位置【下标从0开始】
		（1）当前要插入的位置已存在时，会自动将当前位置及之后的元素全部后移进行插入
		（2）参数index的值不能大于当前list的容量，即下标必须从0开始
		（3）由于ArrayList对象初始化时不包含任何元素，因此size的值为依旧为0，所以，即使在创建list对象时指定了初始化大小，也不可以从任意下标插入（无论是否初始化大小，下标必须从0开始）
		 */
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == '2') {//进一再减一
				list.add(0,-1);//-1插在开头
				if (i == arr.length - 1) {//若最后一个字符,要有进位操作
					list.add(0,1);
				} else {
					++arr[i + 1];//不是最后一个字符，那么对“数组中的”下一个元素+1；也可以写成arr[i + 1]++
				}
			} else if (arr[i] == '3') {
				list.add(0,0);
				if (i == arr.length - 1) {//若最后一个字符,要有进位操作
					list.add(0,1);
				} else {
					++arr[i + 1];
				}
			} else {
				list.add(0,arr[i] - '0');
			}
		}
		StringBuilder stringBuilder = new StringBuilder();
		for (int i = 0; i < list.size(); i++) {
			if (list.get(i) == 1) {
				stringBuilder.append("+").append((int) Math.pow(3, list.size() - 1 - i));//list.size() - 1 - i一种固定写法，自己去画图就懂了
			}
			if (list.get(i) == -1) {
				stringBuilder.append("-").append((int) Math.pow(3, list.size() - 1 - i));
			}
		}
		
		System.out.println(stringBuilder.substring(1));
		System.out.println(stringBuilder.toString());
	}
	
	/**
	 * 适用于5位长的三进制数
	 * @param n
	 */
	public static void violence(int n) {
		int[] s = new int[] {0, 1, -1};
		for (int a = 0; a < 3; a++) {
			for (int b = 0; b < 3; b++) {
				for (int c = 0; c < 3; c++) {
					for (int d = 0; d < 3; d++) {
						for (int e = 0; e < 3; e++) {
							if (s[a] * 81 + s[b] * 27 + s[c] * 9 + s[d] * 3 + s[e] * 1 == n) {
								StringBuilder stringBuilder = new StringBuilder();
								if (s[a] == 1) {
									stringBuilder.append("81");
								}
								if (s[b] == 1) {
									stringBuilder.append("+27");
								}
								if (s[b] == -1) {
									stringBuilder.append("-27");
								}
								if (s[c] == 1) {
									stringBuilder.append("+9");
								}
								if (s[c] == -1) {
									stringBuilder.append("-9");
								}
								if (s[d] == 1) {
									stringBuilder.append("+3");
								}
								if (s[d] == -1) {
									stringBuilder.append("-3");
								}
								if (s[e] == 1) {
									stringBuilder.append("+1");
								}
								if (s[e] == -1) {
									stringBuilder.append("-1");
								}
								if (stringBuilder.charAt(0) == '+' || stringBuilder.charAt(0) == '-') {
									System.out.println(stringBuilder.substring(1));
								} else {
									System.out.println(stringBuilder.toString());
								}
								return;
							}
						}
					}
				}
			}
		}
	}
}
